<?
function print_array($to_print) {
    print "[";
    print implode(", ", $to_print);
    print "]\n";
}

function quicksort($to_sort) {
    $array_length = count($to_sort);
    if ($array_length == 0 or $array_length == 1) {
        return $to_sort;
    }
    else {
        $pivot = array_shift($to_sort);
        $le_pivot = array();
        $gt_pivot = array();
        foreach (array_values($to_sort) as $integral) {
            if ($integral <= $pivot) {
                $le_pivot[] = $integral;
            }
            else {
                $gt_pivot[] = $integral;
            }
        }
        return array_merge(quicksort($le_pivot), array($pivot),
                            quicksort($gt_pivot));
    }
}

function mergesort($array_A, $array_B) {
    // array_shift() returns NULL if array is empty.
    $current_A = array_shift($array_A);
    $current_B = array_shift($array_B);
    $sorted = array();
    // count() should return 0 for a NULL value.
    while (count($array_A) > 0 and count($array_B) > 0) {
        if ($current_A <= $current_B) {
            $sorted[] = $current_A;
            $current_A = array_shift($array_A);
        }
        else {
            $sorted[] = $current_B;
            $current_B = array_shift($array_B);
        }
    }
    if (!$current_A) {
        $sorted[] = $current_B;
    }
    elseif (!$current_B) {
        $sorted[] = $current_A;
    }
    elseif ($current_A <= $current_B) {
        $sorted[] = $current_A;
        $sorted[] = $current_B;
    }
    else {
        $sorted[] = $current_B;
        $sorted[] = $current_A;
    }
    return array_merge($sorted, $array_A, $array_B);
}


$random_ints = range($argv[1], 1);
if (count($random_ints) > 1) {
    $split_arrays = array_chunk($random_ints, ceil(count($random_ints)/2.0));
    $array_A = $split_arrays[0];
    $array_B = $split_arrays[1];
}
else {
    $array_A = $random_ints;
    $array_B = array();
}
$sorted_A = quicksort($array_A);
$sorted_B = quicksort($array_B);
print_array(mergesort($sorted_A, $sorted_B));
?>
